#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#pragma GCC diagnostic ignored "-Wformat="

//#define DEBUG
#define PQUEUE_IMPLEMENTATION
#include "pqueue.h"

#include "acutest.h"

#ifndef UNUSED
#define UNUSED(X) ((void)(X))
#endif

#ifndef E
#define E(X) (sizeof(X)/sizeof(X[0]))
#endif

#define START_SIZE 10

//******************************************************************************
// static helper functions
//******************************************************************************
static pqueue_node_t *resizer(pqueue_node_t *nodes, size_t size)
{
    return realloc(nodes, size);
}

static pqueue_node_t *fake_resizer(pqueue_node_t *nodes, size_t size)
{
    UNUSED(nodes);
    UNUSED(size);

    return NULL;
}

//******************************************************************************
// test cases
//******************************************************************************

static void test_simple_pqueue_creation(void)
{
    pqueue_heap_t *h = pqueue_create(START_SIZE);
    TEST_CHECK(h != NULL);
    TEST_CHECK(h->length == 0);
    TEST_CHECK(h->size == START_SIZE);
    TEST_CHECK(h->resizer == NULL);
    TEST_CHECK(h->nodes != NULL);
    pqueue_destroy(&h);
    TEST_CHECK(h == NULL);
}

static void test_extended_pqueue_creation(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t *nodes = malloc(sizeof(pqueue_node_t) * START_SIZE);

    h = pqueue_create_ex(NULL, NULL, START_SIZE, NULL);
    TEST_CHECK(h != NULL);
    TEST_CHECK(h != &heap_store);
    TEST_CHECK(h->length == 0);
    TEST_CHECK(h->size == START_SIZE);
    TEST_CHECK(h->resizer == NULL);
    TEST_CHECK(h->nodes != NULL);
    TEST_CHECK(h->dynamic_heap);
    TEST_CHECK(h->dynamic_nodes);

    pqueue_destroy(&h);
    TEST_CHECK(h == NULL);

    h = pqueue_create_ex(&heap_store, NULL, START_SIZE, NULL);
    TEST_CHECK(h != NULL);
    TEST_CHECK(h == &heap_store);
    TEST_CHECK(h->length == 0);
    TEST_CHECK(h->size == START_SIZE);
    TEST_CHECK(h->resizer == NULL);
    TEST_CHECK(h->nodes != NULL);
    TEST_CHECK(h->nodes == heap_store.nodes);
    TEST_CHECK(!h->dynamic_heap);
    TEST_CHECK(h->dynamic_nodes);

    pqueue_destroy(&h);
    TEST_CHECK(h == NULL);
    TEST_CHECK(heap_store.length == 0);
    TEST_CHECK(heap_store.size == 0);
    TEST_CHECK(heap_store.nodes == NULL);
    TEST_CHECK(heap_store.resizer == NULL);
    TEST_CHECK(!heap_store.dynamic_heap);
    TEST_CHECK(!heap_store.dynamic_nodes);

    h = pqueue_create_ex(&heap_store, nodes, START_SIZE, resizer);
    TEST_CHECK(h != NULL);
    TEST_CHECK(h == &heap_store);
    TEST_CHECK(h->length == 0);
    TEST_CHECK(h->size == START_SIZE);
    TEST_CHECK(h->resizer == resizer);
    TEST_CHECK(h->nodes != NULL);
    TEST_CHECK(h->nodes == heap_store.nodes);
    TEST_CHECK(!h->dynamic_heap);
    TEST_CHECK(!h->dynamic_nodes);

    pqueue_destroy(&h);
    TEST_CHECK(h == NULL);
    TEST_CHECK(heap_store.length == 0);
    TEST_CHECK(heap_store.size == 0);
    TEST_CHECK(heap_store.nodes == NULL);
    TEST_CHECK(heap_store.resizer == NULL);
    TEST_CHECK(!heap_store.dynamic_heap);
    TEST_CHECK(!heap_store.dynamic_nodes);
    free(nodes);
}

static void test_pqueue_insertion(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t nodes[START_SIZE], *node;
    pqueue_err_t err;

    h = pqueue_create_ex(&heap_store, nodes, START_SIZE, fake_resizer);
    TEST_CHECK(h == &heap_store);
    TEST_CHECK(h->nodes == nodes);
    TEST_CHECK(!h->dynamic_heap);
    TEST_CHECK(!h->dynamic_nodes);

    struct { pri_t pri; int data; } data[] = {
        { .pri = 5, .data = 50, },
        { .pri = 7, .data = 70, },
        { .pri = 2, .data = 20, },
        { .pri = 8, .data = 80, },
    };
    pri_t expected[] = { 5, 5, 2, 2, };
    for (int i = 0; i < E(data); i++)
    {
        err = pqueue_insert(h, data[i].pri, &data[i].data);
        TEST_CHECK(err == PQ_OK);
        node = pqueue_peek(h);
        TEST_CHECK(node->priority == expected[i]);
    }
    TEST_CHECK(heap_store.length == 4);

    pqueue_destroy(&h);
    TEST_CHECK(h == NULL);
    TEST_CHECK(heap_store.length == 0);
    TEST_CHECK(heap_store.size == 0);
    TEST_CHECK(heap_store.nodes == NULL);
    TEST_CHECK(heap_store.resizer == NULL);
    TEST_CHECK(!heap_store.dynamic_heap);
    TEST_CHECK(!heap_store.dynamic_nodes);
}

static void test_pqueue_removal(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t nodes[START_SIZE], node;
    pqueue_err_t err;

    h = pqueue_create_ex(&heap_store, nodes, START_SIZE, fake_resizer);

    struct { pri_t pri; int data; } data[] = {
        { .pri = 5, .data = 50, },
        { .pri = 7, .data = 70, },
        { .pri = 2, .data = 20, },
        { .pri = 8, .data = 80, },
    },
    expected[] = {
        { .pri = 2, .data = 20, },
        { .pri = 5, .data = 50, },
        { .pri = 7, .data = 70, },
        { .pri = 8, .data = 80, },
    };
    for (int i = 0; i < E(data); i++)
    {
        err = pqueue_insert(h, data[i].pri, &data[i].data);
        TEST_CHECK(err == PQ_OK);
    }
    TEST_CHECK(heap_store.length == 4);

    pri_t last_priority = 0;
    size_t expected_length = heap_store.length, i = 0;
    while ((err = pqueue_remove(h, &node)) == PQ_OK)
    {
        TEST_CHECK(node.priority >= last_priority);
        last_priority = node.priority;
        TEST_CHECK(--expected_length == heap_store.length);
        TEST_CHECK(expected[i].pri == node.priority);
        TEST_MSG("expected[i].pri = %u, node.priority = %u", expected[i].pri, node.priority);
        TEST_CHECK(expected[i].data == *(int *)node.data);
        TEST_MSG("expected[i].data = %d, node.data = %d", expected[i].data, *(int *)node.data);
        i++;
    }
    TEST_CHECK(err == PQ_EMPTY_HEAP);

    pqueue_destroy(&h);
}

static void test_pqueue_insertion_removal(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t nodes[START_SIZE], node;
    pqueue_err_t err;

    h = pqueue_create_ex(&heap_store, nodes, START_SIZE, fake_resizer);

    struct { pri_t pri; int data; } data[] = {
        { .pri = 5,  .data = 50,  },
        { .pri = 7,  .data = 70,  },
        { .pri = 2,  .data = 20,  },
        { .pri = 8,  .data = 80,  },
        { .pri = 10, .data = 100, },
        { .pri = 3,  .data = 30,  },
        { .pri = 1,  .data = 10,  },
        { .pri = 4,  .data = 40,  },
        { .pri = 6,  .data = 60,  },
        { .pri = 9,  .data = 90,  },
    },
    deleted[] = {
        { .pri = 5, .data = 50, },
        { .pri = 2, .data = 20, },
        { .pri = 1, .data = 10, },
        { .pri = 3, .data = 30, },
    },
    expected[] = {
        { .pri = 4,  .data = 40,  },
        { .pri = 6,  .data = 60,  },
        { .pri = 7,  .data = 70,  },
        { .pri = 8,  .data = 80,  },
        { .pri = 9,  .data = 90,  },
        { .pri = 10, .data = 100, },
    };
    size_t d = 0;
    for (int i = 0; i < E(data); i++)
    {
        err = pqueue_insert(h, data[i].pri, &data[i].data);
        if ((i % 3) == 0)
        {
            err = pqueue_remove(h, &node);
            TEST_CHECK(err == PQ_OK);
            TEST_CHECK(deleted[d].pri == node.priority);
            TEST_CHECK(deleted[d].data == *(int *)node.data);
            d++;
        }
        TEST_CHECK(err == PQ_OK);
    }
    TEST_CHECK(heap_store.length == 6);

    pri_t last_priority = 0;
    size_t expected_length = heap_store.length, i = 0;
    while ((err = pqueue_remove(h, &node)) == PQ_OK)
    {
        TEST_CHECK(node.priority >= last_priority);
        last_priority = node.priority;
        TEST_CHECK(--expected_length == heap_store.length);
        TEST_CHECK(expected[i].pri == node.priority);
        TEST_CHECK(expected[i].data == *(int *)node.data);
        i++;
    }

    pqueue_destroy(&h);
}

static void test_dynamic_growth(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t node;
    pqueue_err_t err;

    h = pqueue_create_ex(&heap_store, NULL, START_SIZE / 3, NULL);
    TEST_CHECK(h == &heap_store);
    TEST_CHECK(!h->dynamic_heap);
    TEST_CHECK(h->dynamic_nodes);

    struct { pri_t pri; int data; } data[] = {
        { .pri = 5,  .data = 50,  },
        { .pri = 7,  .data = 70,  },
        { .pri = 2,  .data = 20,  },
        { .pri = 8,  .data = 80,  },
        { .pri = 10, .data = 100, },
        { .pri = 3,  .data = 30,  },
        { .pri = 1,  .data = 10,  },
        { .pri = 4,  .data = 40,  },
        { .pri = 6,  .data = 60,  },
        { .pri = 9,  .data = 90,  },
    };
    pri_t expected[] = { 5, 5, 2, 2, 2, 2, 1, 1, 1, 1 };
    for (int i = 0; i < E(data); i++)
    {
        err = pqueue_insert(h, data[i].pri, &data[i].data);
        TEST_CHECK(err == PQ_OK);
        node = *pqueue_peek(h);
        TEST_CHECK(node.priority == expected[i]);
    }
    TEST_CHECK(heap_store.length == 10);
    TEST_CHECK(heap_store.size == 12);

    pqueue_destroy(&h);
}

static void test_static_growth(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t *nodes = malloc(sizeof(pqueue_node_t) * START_SIZE / 3), node;
    pqueue_err_t err;

    h = pqueue_create_ex(&heap_store, nodes, START_SIZE / 3, resizer);
    TEST_CHECK(h == &heap_store);
    TEST_CHECK(!h->dynamic_heap);
    TEST_CHECK(!h->dynamic_nodes);

    struct { pri_t pri; int data; } data[] = {
        { .pri = 5,  .data = 50,  },
        { .pri = 7,  .data = 70,  },
        { .pri = 2,  .data = 20,  },
        { .pri = 8,  .data = 80,  },
        { .pri = 10, .data = 100, },
        { .pri = 3,  .data = 30,  },
        { .pri = 1,  .data = 10,  },
        { .pri = 4,  .data = 40,  },
        { .pri = 6,  .data = 60,  },
        { .pri = 9,  .data = 90,  },
    };
    pri_t expected[] = { 5, 5, 2, 2, 2, 2, 1, 1, 1, 1 };
    for (int i = 0; i < E(data); i++)
    {
        err = pqueue_insert(h, data[i].pri, &data[i].data);
        TEST_CHECK(err == PQ_OK);
        node = *pqueue_peek(h);
        TEST_CHECK(node.priority == expected[i]);
    }
    TEST_CHECK(heap_store.length == 10);
    TEST_CHECK(heap_store.size == 12);

    free(h->nodes);
    pqueue_destroy(&h);
}

static void test_failed_growth(void)
{
    pqueue_heap_t *h, heap_store;
    pqueue_node_t *nodes = malloc(sizeof(pqueue_node_t) * START_SIZE / 3);
    pqueue_err_t err;

    h = pqueue_create_ex(&heap_store, nodes, START_SIZE / 3, fake_resizer);
    TEST_CHECK(h == &heap_store);
    TEST_CHECK(!h->dynamic_heap);
    TEST_CHECK(!h->dynamic_nodes);

    struct { pri_t pri; int data; } data[] = {
        { .pri = 5,  .data = 50,  },
        { .pri = 7,  .data = 70,  },
        { .pri = 2,  .data = 20,  },
        { .pri = 8,  .data = 80,  },
        { .pri = 10, .data = 100, },
        { .pri = 3,  .data = 30,  },
        { .pri = 1,  .data = 10,  },
        { .pri = 4,  .data = 40,  },
        { .pri = 6,  .data = 60,  },
        { .pri = 9,  .data = 90,  },
    };
    for (int i = 0; i < E(data); i++)
    {
        err = pqueue_insert(h, data[i].pri, &data[i].data);
        if (i < 3) { TEST_CHECK(err == PQ_OK); }
        if (i == 3) { TEST_CHECK(err == PQ_RESIZE_ERR); break; }
    }
    TEST_CHECK(heap_store.length == 3);
    TEST_CHECK(heap_store.size == 3);

    free(nodes);
    pqueue_destroy(&h);
}

TEST_LIST =
{
    { "simple pqueue creation",         test_simple_pqueue_creation   },
    { "extended pqueue creation",       test_extended_pqueue_creation },
    { "pqueue insertion",               test_pqueue_insertion         },
    { "pqueue removal",                 test_pqueue_removal           },
    { "pqueue mixed insertion/removal", test_pqueue_insertion_removal },
    { "dynamic growth",                 test_dynamic_growth           },
    { "static growth",                  test_static_growth            },
    { "failed growth",                  test_failed_growth            },
    { NULL, NULL }
};
